This invention relates generally to methods and apparatus for modulation coding of data.
Modulation codes are employed in data storage systems to eliminate undesirable bit-patterns in the recording data, for example bit-sequences which give rise to errors in the reproduction process. One example of an undesirable bit-sequence is a long run of bits of the same value. Another example is a long run of bits of the same value in alternating positions in the bit sequence, i.e. in either the odd (O) or even (E) interleave of a bit stream . . . EOEOEO . . . . For instance, a long sequence of the form 0a0b0c0d0 . . . , where a, b, c, etc. can be either 0 or 1, would be generally undesirable. Modulation codes impose some form of constraint on the occurrence of undesirable bit-patterns in the encoded bit-sequence. For example, some modulation codes impose a so-called j-constraint, whereby the maximum length of a run of consecutive 1's in the encoded sequence is limited to the predetermined value j. Other modulation codes impose a constraint on the maximum run-length of consecutive 0's. This is referred to as a k- or G-constraint, whereby the maximum run-length of consecutive 0's is limited to the value k or G respectively. An example of the latter code-type is provided by the PRML (G,I) codes used in PRML (partial-response maximum likelihood) based recording systems such as tape drives and optical storage systems. In addition to the “global” or G-constraint, these codes impose an “interleave” or I-constraint. This limits the maximum run-length of 0's in each of the odd and even interleaves to the value I. An I-constrained bit-stream is of course necessarily G-constrained with G=2I.
Modulation encoders in data storage systems are generally used in conjunction with precoders. Precoders are digital filters with feedback, and apply some function of the delay operator “D” to an input where D corresponds to the channel bit period T. In communications engineering generally, precoders have been used for various different purposes to effect transmitter-side processing before a signal is transmitted over a communications channel or recorded on a storage medium. For example, preceding has been used in partial-response signaling as a channel equalization technique. In a different application, rate-1 precoders have been used to improve the properties of linear error-correcting (ECC) codes such as convolutional codes in order to improve the bit-error rate performance of partial-response systems. For instance, 1/(1⊕D) precoders (where ⊕ represents modulo 2 addition) have been used with convolutional encoders to improve transmission reliability over noisy partial-response channels of type (1−D) and (1+D) by Viterbi decoding on the combined code-channel trellis. The 1/(1⊕D) precoder is also known to transform NRZI (non-return to zero inverse) symbols in to NRZ (non-return to zero) symbols. Another example is discussed in “Effect of Precoding on the Convergence of Turbo Equalization for Partial Response Channels,” K. R. Narayanan, IEEE Journal on Selected Areas in Commun., vol. 19, pp. 686-698, April 2001. Here, rate-1 recursive convolutional codes with transfer function 1/g(D), where g(D) is a polynomial 1⊕Σjw-1Dij with weight w, are employed for precoding in partial-response systems to improve the error-rate performance of iterative detection/decoding schemes, also known as turbo-equalization schemes. However, with modulation codes, which are generally non-linear codes, precoders are employed for an entirely different purpose to the pre-equalization of partial response systems or improvement of properties of linear ECC codes as just described. Specifically, precoders are employed in modulation coding to translate the constraints imposed by the modulation code into desired constraints at the input to the recording channel. Only two types of precoder have been used in modulation coding, namely the 1(1⊕D) precoder and the 1(1⊕D2) precoder. Almost all practical modulation coding schemes in data storage use such precoders.
Currently most data storage systems employ forward concatenation schemes, whereby modulation coding is performed after error-correction coding (ECC) to protect the integrity of the stored data. The alternative is reverse concatenation (RC), where the modulation coding is performed before error-correction coding. Error propagation is reduced in RC modulation schemes because the ECC decoder operates before the modulation decoder on reproduction. That is, if the ECC decoder makes no errors, there is no error propagation through the modulation decoder. Hence, RC allows the use of efficient, higher rate modulation codes without suffering from performance degradation due to error propagation. Efficient high-rate modulation codes are usually generated by a technique known as enumerative encoding which allows the coding to be implemented in an algorithmic manner. Enumerative encoding is described in detail in “Enumerative Source Encoding”, T. M. Cover, IEEE Trans. Inform. Theory, Vol. 19, pp. 73-77, January 1973. In simple terms, enumerative encoding is a process of mapping input words to output codewords based on lexicographic ordering of the codewords. That is, if a set of X binary codewords are ordered according to binary value, then each codeword can be assigned a number from 1 to X according to its position in the ordered set. If each of these assigned numbers 1 to X then defines the value of a binary input word, each of the X binary input words is associated with a corresponding codeword. Enumerative encoding is the process of mapping input words to output codewords in accordance with this type of scheme. While the underlying encoding principle is simple enough, the problem in practice lies in designing an efficient encoder for generating the codewords from the binary input words. If there are 2100 codewords for example, then the need for an efficient encoder design is readily apparent.
Enumerative encoders that impose either a k-constraint or a j-constraint were first proposed by W. H. Kautz in “Fibonacci Codes for Synchronization Control”, IEEE Trans. Inform. Theory, Vol. 11, pp. 284-292, April 1965. The principles of these Fibonacci codes will be explained below. Enumerative encoders that satisfy a k-constraint or a j-constraint with a short sliding-window implementation of encoding and decoding have been proposed by Immink in “A Practical Method for approaching the Channel Capacity of Constrained Channels”, IEEE Trans. Inform. Theory, Vol. 43, pp. 1389-1399, September 1997. These types of encoders are used together with the 1/(1⊕D)-type precoders discussed above. Enumerative encoding algorithms have also been proposed for (d,k) constraints, where d represents the minimum number of consecutive 0's between two 1's, in “Encoding of dklr-sequences Using One Weight Set”, Patrovics et al., IEEE Trans. Inform. Theory, Vol. 42, pp. 1553-1554, September 1996. Enumerative encoding algorithms for PRML (G,I) constraints for the special case of G=2I are described in “High-Rate Modulation Codes for Reverse Concatenation”, Blaum et al., IEEE Trans. Magn., Vol. 43, No. 2, pp. 740-743, February 2007, and “Enumerative Encoding with Non-uniform Modulation Constraints”, Blaum et al., IEEE Int'l. Symp. on Information Theory, ISIT 2007, Nice, France, June 2007, pp. 1831-1835. These types of encoders are used together with the 1/(1⊕D2)-type precoders discussed above.
With PRML (G,I) codes, the G-constraint at the input of the 1/(1⊕D2) precoder translates into three constraints at the output of the 1/(1⊕D2) precoder. Firstly, the maximum run-length of 0's is limited to c0=G+2. Secondly, the maximum run-length of 1's is limited to c1=G+2. Thirdly, the maximum number of alternating bits . . . 010101010101 . . . is limited to ca=G+2. The I-constraint at the input of the 1/(1⊕D2) precoder translates into two constraints at the output of the 1/(1⊕D2) precoder. Firstly, the maximum run-length of 0's in each of the odd and even interleaves is limited to i0=I+1. Secondly, the maximum run-length of 1's in each of the odd and even interleaves is limited to i1=I+1.
A problem with the foregoing encoders, and enumerative encoding generally, is that very few constraints can be imposed in this way in an algorithmic fashion. In practice, however, it is desirable to impose a variety of constraints at the input to a recording channel. One important constraint is the variable frequency oscillator (VFO) constraint. This constraint limits the maximum length of patterns of the type . . . 0011001100111 . . . , known as the VFO pattern at the fundamental frequency 1/(4T) at the centre of the Nyquist band, in the recorded encoded data. This constraint cannot currently be achieved with modulation coding based on high-rate (G,I) codes as discussed above. To achieve this constraint at reasonable code-rates, more complex coding schemes have been employed. In particular, current LTO (Linear Tape Open) tape drives employ a rate 16/17 TC (twins-constrained) modulation code which is described in general terms in U.S. Pat. No. 6,985,320. This rate 16/17 code ensures that each codeword has an isolated peak (NRZI pattern 010) and imposes four constraints (j, k, t, a). Here, j and k specify the maximum run-lengths of 1's and 0's respectively. The t-constraint limits the maximum number of consecutive twins, where a twin is either 00 or 11. The a-constraint limits the maximum run-length of alternating binary symbols. The LTO modulation encoder uses a 1/(1⊕D) precoder to translate all these constraints into the desired recording channel constraints. Here, the a-constraint is translated into the VFO constraint. Specifically, the LTO rate 16/17 code limits the maximum length of the VFO pattern to CVFO=25. This is achieved by limiting the run-length of alternating bits to a=24 at the input of the 1/(1⊕D) precoder.
The constraints imposed by the LTO rate 16/17 code can be viewed as equivalent to the constraints G=13, I=11 and M=23, where M is the maximum run-length of 1's and is related to the VFO constraint by CVFO=M+2 (see section V of “Maximum Transition Run Codes for Generalized Partial Response Channels, Cideciyan et al., IEEE J. Select. Areas Commun., Vol. 19, No. 4, pp. 619-634, April 2001 for an explanation of the relationship between constraints here. (G,I,M) codes are mentioned in “Digital Baseband Transmission and Recording”, J. W. M. Bergmans, Kluwer Academic Publishers, 1996, page 171, referencing “A PRML System for Digital Magnetic Recording”, Cideciyan et al., IEEE J. Select. Areas Commun., Vol. 10, No. 1, pp. 38-56, January 1992). Thus, the a-constraint in the LTO rate 16/17 code is equivalent to limiting the number of consecutive 1's at the input of a 1/(1⊕D2) precoder to M=a−1=23. The first rate 8/9 PRML code implemented in IBM's disk drives satisfied the constraints G=4, I=4 and M=9 as described in the Cideciyan et al paper referenced above. The code rates 8/9 and 16/17 are low by the standards of the PRML (G,I) encoders based on enumerative coding discussed above, but the latter do not of course offer the VFO constraint.
In view of the above, it would be desirable to provide improved modulation coding systems allowing imposition of the VFO constraint.